HackerRank The Coin Change Problem

https://www.hackerrank.com/challenges/coin-change/problem

解答

code: python

#!/bin/python3

import math

import os

import random

import re

import sys

# Complete the 'getWays' function below.

# The function is expected to return a LONG_INTEGER.

# The function accepts following parameters:

# 1. INTEGER n

# 2. LONG_INTEGER_ARRAY c

'''

2 5 3 6

0 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0

dp2 += dp0

dp3 += dp1

dp4 += dp2

dp5 += dp3

dp6 += dp4

dp7 += dp5

dp8 += dp6

dp9 += dp7

dp10 += dp8

2 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1

dp5 += dp0

dp6 += dp1

dp7 += dp2

dp8 += dp3

dp9 += dp4

dp10 += dp5

5 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 2

dp3 += dp0

dp4 += dp1

dp5 += dp2

dp6 += dp3

dp7 += dp4

dp8 += dp5

dp9 += dp6

dp10 += dp7

3 1, 0, 1, 1, 1, 2, 2, 2, 3, 3, 4

dp6 += dp0

dp7 += dp1

dp8 += dp2

dp9 += dp3

dp10 += dp4

6 1, 0, 1, 1, 1, 2, 3, 2, 4, 4, 5

'''

def getWays(n, c):

# dpi := Total number of ways to make an amount i

dp = 0 * (n+1)

dp0 = 1

for i in range(len(c)):

for j in range(ci, n+1):

dpj += dp[j-ci]

return dpn

if __name__ == '__main__':

fptr = open(os.environ'OUTPUT_PATH', 'w')

first_multiple_input = input().rstrip().split()

n = int(first_multiple_input0)

m = int(first_multiple_input1)

c = list(map(int, input().rstrip().split()))

# Print the number of ways of making change for 'n' units using coins having the values given by 'c'

ways = getWays(n, c)

fptr.write(str(ways) + '\n')

fptr.close()

テーマ

#dp

提出

code: python

#!/bin/python3

import math

import os

import random

import re

import sys

# Complete the 'getWays' function below.

# The function is expected to return a LONG_INTEGER.

# The function accepts following parameters:

# 1. INTEGER n

# 2. LONG_INTEGER_ARRAY c

'''

2 5 3 6

- sort

c = 2,3,5,6

- dpij := use c:i and use j numbers

-- dp00 = 0,

-- dp01 = 2,

-- dp02 = 4,

-- dp03 = 6,

-- dp04 = 8,

-- dp05 = 10,

-- dp10 = 0,

-- dp11 = dp10 + c1 = 3, dp00 + c1 = 3

-- dp12 = dp11 + c1 = 6, dp01 + c1 = 5

-- dp13 = dp12 + c1 = 9,8, dp02 + c1 = 7

-- dp05 = 10,

'''

def getWays(n, c):

# Write your code here

c.sort()

max_use = math.ceil(n/c0) + 1

dp = [[[]] * max_use for _ in range(len(c))]

for i in range(max_use):

dp0i.append(i*c0)

for i in range(len(c)):

dpi0.append(0)

for i in range(len(c)):

for j in range(1, max_use):

for v1 in dpij-1:

dpij.append(v1+ci)

for v2 in dpi-1j-1:

dpij.append(v2+ci)

print(dp)

if __name__ == '__main__':

fptr = open(os.environ'OUTPUT_PATH', 'w')

first_multiple_input = input().rstrip().split()

n = int(first_multiple_input0)

m = int(first_multiple_input1)

c = list(map(int, input().rstrip().split()))

# Print the number of ways of making change for 'n' units using coins having the values given by 'c'

ways = getWays(n, c)

fptr.write(str(ways) + '\n')

fptr.close()